//https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array/
class Solution {
public:
    long long sums(long long begin, long long n)
    {
        return (begin + n) * (n - begin + 1) / 2;
    }
    int maxValue(int n, int index, int maxSum) {
        int left = 1, right = maxSum;
        while (left < right)
        {
            long long mid = left + (right - left + 1) / 2;
            long long sum = mid;
            if (n - 1 - index >= mid - 1)sum += sums(1, mid - 1) + n - index - mid;
            else sum += sums(mid - n + index + 1, mid - 1);
            if (index >= mid - 1)sum += sums(1, mid - 1) + index - mid + 1;
            else sum += sums(mid - 1 - index + 1, mid - 1);
            if (maxSum < sum)right = mid - 1;
            else left = mid;
        }
        return left;
    }
};